package com.Oct_Seven;

/**
 * 1219. 黄金矿工
 * 你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
 *
 * 为了使收益最大化，矿工需要按以下规则来开采黄金：
 *
 * 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
 * 矿工每次可以从当前位置向上下左右四个方向走。
 * 每个单元格只能被开采（进入）一次。
 * 不得开采（进入）黄金数目为 0 的单元格。
 * 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/path-with-maximum-gold
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/07 14:44
 */

public class Solution1219 {

    int ans=0;
    int[][] grid;
    public int getMaximumGold(int[][] grid) {
        this.grid=grid;
        for (int i=0;i<grid.length;i++)
        {
            for (int j=0;j<grid[0].length;j++)
            {
                if (grid[i][j]!=0)
                {
                    dfs(i,j,0);
                }
            }
        }
        return ans;
    }

    public void dfs(int i,int j,int gold){
        if (i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]==0) return;
        int temp=grid[i][j];
        gold+=temp;
        grid[i][j]=0;
        ans=Math.max(ans,gold);
        dfs(i-1,j,gold);
        dfs(i+1,j,gold);
        dfs(i,j-1,gold);
        dfs(i,j+1,gold);
        gold-=temp;
        grid[i][j]=temp;
    }

    public static void main(String[] args) {
        Solution1219 solution1219=new Solution1219();
        System.out.println(solution1219.getMaximumGold(new int[][]{
                {0,6,0},
                {5,8,7},
                {0,9,0}
        }));
    }
}
